#pragma once
#include<utility>
#include<vector>
#include"LCS.h"

template<class iterator>
void pushingLCS(SignedArray<int> &max_distance, iterator first_begin, iterator first_end, iterator second_begin, iterator second_end,
	int editorDistance){
	size_t size_first = first_end - first_begin;
	size_t size_second = second_end - second_begin;
	
	max_distance[0] = maxPrefix(first_begin, first_end, second_begin, second_end);
	for (int Distance = 1; Distance <= editorDistance; ++Distance)
		lcsStep(max_distance, Distance, first_begin, first_end, second_begin, second_end);
}


template<class iterator1>
void Find_Editor_Path(iterator1 first_begin, iterator1 first_end,
			 iterator1 second_begin, iterator1 second_end,
			 int editorDistance,
			 std::vector<std::pair<char, long long> >& editingWay) {
	std::reverse_iterator<iterator1> first_rbegin(first_end), first_rend(first_begin),
		second_rbegin(second_end), second_rend(second_begin);
	
	int first_size = first_end - first_begin;
	int second_size = second_end - second_begin;
	if (editorDistance == 0){
		for (iterator1 it = first_begin; it != first_end; ++it){
			editingWay.push_back(make_pair(' ', *it));

		}
		return;
	}
	if (editorDistance == 1){
		int current_prefix = maxPrefix(first_begin, first_end, second_begin, second_end);
		for (int i = 0; i < current_prefix; ++i){
			editingWay.push_back({ ' ', *(first_begin + i) });
		}
		if (first_size == second_size + 1){
			editingWay.push_back({ '-', *(first_begin + current_prefix) });
			for (int j = current_prefix + 1; j < first_size; ++j)
				editingWay.push_back({ ' ', *(first_begin + j) });
		}
		else{
			editingWay.push_back({ '+', *(second_begin + current_prefix) });
			for (int j = current_prefix; j < first_size; ++j)
				editingWay.push_back({ ' ', *(first_begin + j) });
		}
		return;
	}
	if (first_size == 0){
		for (iterator1 it = second_begin; it != second_end; ++it){
			editingWay.push_back(make_pair('+', *it));
		}
		return;
	}
	if (second_size == 0){
		for (iterator1 it = first_begin; it != first_end; ++it){
			editingWay.push_back(make_pair('-', *it));
		}
		return;
	}
	
	SignedArray<int> forward_pushing(4 * (first_size)+4 * (second_size)+1,
		2 * first_size + 2 * second_size);
	pushingLCS(forward_pushing,first_begin, first_end, second_begin, second_end, (editorDistance)/ 2);
	SignedArray<int> reverse_pushing(4 * (first_size)+4 * (second_size)+1,
		2 * first_size + 2 * second_size);
	pushingLCS(reverse_pushing,first_rbegin, first_rend, second_rbegin, second_rend, (editorDistance + 1) / 2);
	
	
	int distance_for_shifting = first_size - second_size;
	for (int diag = -(editorDistance / 2); diag <= (editorDistance)/2; ++diag){
		if (forward_pushing[diag] + reverse_pushing[-diag+distance_for_shifting] >= first_size && forward_pushing[diag] <= first_size && 
			reverse_pushing[-diag + distance_for_shifting] <= first_size){
			int right_forward_x = forward_pushing[diag];
			int right_forward_y = right_forward_x - (diag);
			int right_back_x = first_size - right_forward_x;
			int right_back_y = second_size - right_forward_y;
			
				
				Find_Editor_Path(first_begin, first_begin + right_forward_x, second_begin, second_begin + right_forward_y,
					(editorDistance) / 2, editingWay);
				
				Find_Editor_Path(first_begin + right_forward_x, first_end, second_begin + right_forward_y, second_end,
					(editorDistance + 1) / 2, editingWay);
				break;
		}
	}
}
